package com.c2b.algorithm.leetcode.base;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode.cn/problems/simplify-path/description/?envType=study-plan-v2&envId=top-interview-150">简化路径(Simplify Path)</a>
 * <p>给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。</p>
 * <p>
 * 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。
 * </p>
 * <p>
 * 请注意，返回的 规范路径 必须遵循下述格式：
 * <ul>
 *     <li>始终以斜杠 '/' 开头。</li>
 *     <li>两个目录名之间必须只有一个斜杠 '/' 。</li>
 *     <li>最后一个目录名（如果存在）不能 以 '/' 结尾。</li>
 *     <li>此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。</li>
 * </ul>
 * 返回简化后得到的 规范路径 。
 * </p>
 * <p>
 *     <b>示例：</b>
 *     <pre>
 * 示例 1：
 *      输入：path = "/home/"
 *      输出："/home"
 *      解释：注意，最后一个目录名后面没有斜杠。
 *
 * 示例 2：
 *      输入：path = "/../"
 *      输出："/"
 *      解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。
 *
 * 示例 3：
 *      输入：path = "/home//foo/"
 *      输出："/home/foo"
 *      解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
 *
 * 示例 4：
 *      输入：path = "/a/./b/../../c/"
 *      输出："/c"
 *     </pre>
 * </p>
 * <p>
 *     <b>提示：</b>
 *     <ul>
 *         <li>1 <= path.length <= 3000</li>
 *         <li>path 由英文字母，数字，'.'，'/' 或 '_' 组成。</li>
 *         <li>path 是一个有效的 Unix 风格绝对路径。</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/12 9:37
 */
public class LC0071SimplifyPath_M {

    static class Solution {
        public String simplifyPath(String path) {
            // 根据'/'进行拆分:
            // 1. 空字符串。例如当出现多个连续的 /，就会分割出空字符串；
            // 2.一个点 '.'；
            // 3.两个点 '..';
            // 4.只包含英文字母、数字或 _的目录名。
            String[] split = path.split("/");
            // 先进先出，模拟栈
            Deque<String> deque = new LinkedList<>();
            for (String s : split) {
                // 「两个点」时，需要将目录切换到上一级，因此只要栈不为空，我们就弹出栈顶的目录。
                if (s.equals("..")) {
                    if (!deque.isEmpty()) {
                        deque.pollLast();
                    }
                } else {
                    // 对于「空字符串」以及「一个点」，我们实际上无需对它们进行处理，因为「空字符串」没有任何含义，而「一个点」表示当前目录本身，我们无需切换目录。
                    if (!s.equals(".") && !s.equals("")) {
                        // 「目录名」时，就把它放入栈
                        deque.addLast(s);
                    }
                }
            }
            StringBuilder ret = new StringBuilder();
            if (!deque.isEmpty()) {
                while (!deque.isEmpty()) {
                    ret.append("/").append(deque.pollFirst());
                }
            } else {
                ret.append("/");
            }
            return ret.toString();
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.simplifyPath("/home/"));
        System.out.println(solution.simplifyPath("/../"));
        System.out.println(solution.simplifyPath("/home//foo/"));
        System.out.println(solution.simplifyPath("/a/./b/../../c/"));
    }
}
